/*
 * @Author: 缄默
 * @Date: 2021-12-09 19:57:17
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-09 20:52:32
 */

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void hanoi(int n);
void func(int n, string from, string mid, string to);

int step1(vector<int>& arr);
int process(vector<int>& arr, int i, int from, int mid, int to);

int step2(vector<int>& arr);

int main() {
    //hanoi(3);
    vector<int> arr({3, 3});
    cout << step1(arr) << endl;
    cout << step2(arr) << endl;

    return 0;
}

void hanoi(int n) {
    if (n > 0) {
        func(n, "left", "mid", "right");
    }
}

void func(int n, string from, string mid, string to) {
    if (n == 1) {
        cout << "move from " << from << " to " << to << endl;
    }
    else {
        func(n - 1, from, to, mid);
        func(1, from, mid ,to);
        func(n - 1, mid , from, to);
    }
}

//判断是不是一个最优过程可以逐个判断他是否满足最优过程
//判断是第几个就判断他是移动的第几步
int step1(vector<int>& arr) {
    if (arr.size() == 0) return -1;
    return process(arr, arr.size() - 1, 1, 2, 3);
}

int process(vector<int>& arr, int i, int from, int mid, int to) {
    if ( i == -1) return 0;
    if (arr[i] != from && arr[i] != to) return -1;
    //圆盘i在左柱上，还没移动，因此要考虑i-1 圆盘的位置
    if (arr[i] == from) {
        //此时i-1个圆盘要移动到mid位置
        return process(arr, i - 1, from, to, mid);
    }
    else {
        //第i个圆盘完成移动 因此步数是移动第i个圆盘所需步数加上剩余的可能的步数
        //判断i-1的状况
        int rest = process(arr, i - 1, mid, from, to);
        //如果剩下的不行 那就返回-1
        if (rest == -1) return -1;
        //可以的话就相加
        return (1 << i) + rest;
    }

}

int step2(vector<int>& arr) {
    if (arr.size() == 0) return -1;
    int from = 1;
    int mid = 2;
    int to = 3;

    int i = arr.size() - 1;
    int res = 0;
    int tmp = 0;
    while (i >= 0) {
        if (arr[i] != from && arr[i] != to) {
            return -1;
        }
        if (arr[i] == to) {
            res += 1 << i;
            tmp = from;
            from = mid;
        }
        else {
            tmp = to;
            to = mid;
        }
        mid = tmp;
        i--;
    }
    return res;
}
